package StackAndQueueSeries;

import java.util.ArrayDeque;
import java.util.Deque;

class MaxSlidingWindowSolution_239 {
    // 使用单调递减队列
    // 维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的
    class MyQueue {
        Deque<Integer> deque = new ArrayDeque<>();

        // 弹出元素：
        // 如果弹出的元素 == 滑动窗口滑走的那个元素，直接弹出；
        // 否则说明这个元素是最大的，但是不知要划走的元素
        public void pop(int value) {
            if (!deque.isEmpty() && deque.peekFirst() == value) {
                deque.removeFirst();
            }
        }

        // 放入元素：
        // 如果放入的元素比单调递减队列的末尾元素大，就弹出末尾元素；
        // 直到value比末尾元素小，再放入value
        public void push(int value) {
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.removeLast();
            }
            deque.addLast(value);
        }

        public int peek() {
            return deque.peekFirst();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        if (nums.length == 1) {
            return nums;
        }

        MyQueue myQueue = new MyQueue();
        int num = 0;
        // 前k个元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.push(nums[i]);
        }
        result[num++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            myQueue.pop(nums[i - k]);
            myQueue.push(nums[i]);
            result[num++] = myQueue.peek();
        }
        return result;
    }
}